'''
https://leetcode.cn/problems/longest-valid-parentheses/description/
'''


class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n < 2: return 0
        dp = [0] * n
        dp[1] = 2 if s[0] == '(' and s[1] == ')' else 0
        for i in range(2, n):
            if s[i] == '(':
                continue
            if s[i - 1] == '(':  # ...()
                dp[i] = 2 + (dp[i - 2] if i - 2 >= 0 else 0)
            else:  # ...?((())))   #a(bcdefg)h
                dp[i] = (2 + dp[i - 1]) if i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(' else 0
                # 好多if啊。。。
                if dp[i] and i - dp[i - 1] - 2 >= 0:
                    dp[i] += dp[i - dp[i - 1] - 2]
        print(dp)
        return max(dp)

    # 简化判断
    def longestValidParentheses2(self, s: str) -> int:
        n = len(s)
        if n < 2: return 0
        dp = [0] * n
        for i in range(1, n):
            if s[i] == ')':
                pre = i - dp[i - 1] - 1
                if pre >= 0 and s[pre] == '(':
                    dp[i] = 2 + dp[i - 1] + (dp[pre - 1] if pre - 1 >= 0 else 0)
        return max(dp)


s = "()(())"
print(Solution().longestValidParentheses(s))
